/**
 * @param {string} ring
 * @param {string} key
 * @return {number}
 */
var findRotateSteps = function (ring: string, key: string) {

    const lRing = ring.length
    const lKey = key.length

    const dp: number[][] = Array.from({length: lKey}, (): number[] => new Array(lRing).fill(-1))

    // init
    for (let ringIndex = 0; ringIndex < ring.length; ringIndex++) {

        const r = ring[ringIndex]
        if (key[0] === r) {
            const diff = Math.abs(ringIndex - 0)
            const steps = Math.min(diff, ring.length - diff) + 1
            dp[0][ringIndex] = steps
        }
    }


    for (let keyIndex = 1; keyIndex < key.length; keyIndex++) {

        const last = dp[keyIndex - 1].map((v, i) => ({steps: v, pos: i}))
            .filter(({steps}) => steps !== -1)

        const k = key[keyIndex]

        for (let ringIndex = 0; ringIndex < ring.length; ringIndex++) {

            const r = ring[ringIndex]
            if (k === r) {


                const allSteps = last.map(({steps, pos}) => {
                    const diff = Math.abs(ringIndex - pos)
                    return Math.min(diff, ring.length - diff) + 1 + steps
                })


                dp[keyIndex][ringIndex] = Math.min(...allSteps)
            }
        }

    }

    return Math.min(...dp[key.length - 1].filter(v => v !== -1))

};

// console.log(findRotateSteps('godding', 'gd'));
console.log(findRotateSteps('ca', 'aaaa'));